package dynamicStudy;

/**
 * 消除冗余，加速计算
 */
public class Summary {
    /**
     * 解题步骤：
     * 一、确定状态（一般是一个数组——一维数组、二维数组）（定海神针）
     *     简单的说，解动态规划的时候需要开一个数组，数组的每个元素[i]或者[i][j]代表什么？
     *          --类似于解数学题目中，X、Y、Z代表什么？
     *     确定状态需要两个意识：
     *          --最后一步（重要）
     *          --子问题（问题一样，规模变小，可以确定状态）
     *     怎么确定是一维还是二维？（重要的问题）
     * 二、转移方程（表达式。通过第一步——最后一步获得）
     * 三、初始条件和边界情况（边界就是数组不要越界）（重要）
     *      为什么需要初始条件和边界：用转移方程算不出来，需要手工定义
     * 四、计算顺序
     *      可能正序也可能逆序，要求计算的时候，上一步已经计算出来了
     */
    /**
     * 动态规划题目特点
     * 1、计数（经常用到加法原理）（++）
     *      比如：（1）有多少种方式走到右下角。（2）有多少种方式选出K个数使得和为sum
     * 2、求最大值或者最小值（最优解）（min max）
     *      比如：（1）从左上角走到右下角路径的最大数字和。（2）最长上升子序列长度
     * 3、求存在性问题（是或者否）(and or)
     *      比如：（1）取石子游戏，先手是否获胜。（2）能不能选取k个数使得和k个数
     */
    /**
     * 总结：
     * 1、计数问题，至关重要，通过最后一步确定转移方程，加上最后一步发生什么样的变化。计数问题一般都是++，或许会用到加法原理
     * 2、按照LeetCode的惯例，子序列（subsequence）不必连续，子数组（subarray）或者子字符串必须连续
     * 3、初始条件很重要，关乎着答案的对错
     * 4、最后异步很重要，怎么才能通过前面的状态到达最后一步。很重要，需要采取什么样的行为。
     */
}
